package mine.code.solution;

import org.junit.Test;

import java.util.Objects;

/**
 * @author caijinnan
 */
public class Solution {


    @Test
    public void run() {
        String s = "acb";
        String t = "ahbgdc";
        System.out.println(isSubsequence(s, t));
    }


    public boolean isSubsequence(String s, String t) {
        if (Objects.equals(s, "")) {
            return true;
        }
        if (t.length() < s.length()) {
            return false;
        }
        boolean[][] dp = new boolean[t.length() ][s.length() ];
        // dp[i][j] = dp[i-1][j]||s[i]==t[j]&&dp[i-1][j-1]
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        dp[0][0] = sChars[0] == tChars[0];
        for (int i = 1; i < tChars.length; i++) {
            dp[i][0] = tChars[i] == sChars[0] || dp[i - 1][0];
        }
        for (int i = 1; i < sChars.length; i++) {
            dp[0][i] = false;
        }
        for (int i = 1; i < tChars.length; i++) {
            for (int j = 1; j < sChars.length; j++) {
                dp[i][j] = dp[i - 1][j] || (tChars[i] == sChars[j] && dp[i - 1][j - 1]);
            }
        }
        return dp[t.length()-1][s.length()-1];
    }
}
